//
// Created by mac on 2023/11/17.
//

// 快乐数
class Solution
{
private:
    // 计算每个位置上的数字的平方和
    inline static int BitSum(int num)
    {
        int ret = 0;
        while(num)
        {
            int t = num % 10;
            ret += t * t;
            num /= 10;
        }
        return ret;
    }

public:
    bool isHappy(int n)
    {
        int slow = n, fast = BitSum(n);
        while(slow != fast)
        {
            slow = BitSum(slow);
            fast = BitSum(BitSum(fast));
        }
        return slow == 1;
    }
};

// 复写零
class Solution
{
public:
    void duplicateZeros(vector<int>& nums)
    {
        // 1、初始化
        int dest = -1, cur = 0, n = nums.size();
        // 2、找到最后一个复写的数
        while(true)
        {
            if(nums[cur]) dest += 1;
            else dest += 2;
            if(dest >= n - 1) break;
            ++cur;
        }
        cout << nums[cur] << endl;
        // 1.5、预处理 -> 让 dest 的下标有效
        if(dest == n)
        {
            if(nums[cur]) --cur, --dest;
            else
            {
                nums[n - 1] = 0;
                dest -= 2;
                cur -= 1;
            }
        }
        // 2、双指针从后往前进行复写操作
        while(cur >= 0)
        {
            if(nums[cur]) nums[dest--] = nums[cur--];
            else
            {
                nums[dest--] = 0;
                nums[dest--] = 0;
                cur--;
            }
        }
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

// 移动零
// 写法一
class Solution
{
public:
    void moveZeroes(vector<int>& nums)
    {
        // 1、下标初始化
        int dest = -1, cur = 0;
        // 2、数组划分
        while(cur < nums.size())
        {
            if(nums[cur])
                swap(nums[++dest], nums[cur++]);
            else
                ++cur;
        }
    }
};

// 写法二
class Solution
{
public:
    void moveZeroes(vector<int>& nums)
    {
        for(int dest = -1, cur = 0; cur < nums.size(); ++cur)
            if(nums[cur]) // 处理 非0 元素
                swap(nums[++dest], nums[cur]);
    }
};

/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/
